home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / agrep / utilities.c.z / utilities.c
C/C++ Source or Header  |  1997-09-09  |  3KB  |  165 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* this file contains various utility functions for accessing
  3.    and manipulating regular expression syntax trees.    */
  4.  
  5. #include <stdio.h>
  6. #include <ctype.h>
  7. #include "re.h"
  8.  
  9. /************************************************************************/
  10. /*                                                                      */
  11. /*  the following routines implement an abstract data type "stack".    */
  12. /*                                                                      */
  13. /************************************************************************/
  14.  
  15. Stack Push(s, v)
  16. Stack *s;
  17. Re_node v;
  18. {
  19.     Stack node;
  20.  
  21.     new_node(Stack, node, node);
  22.     if (s == NULL || node == NULL) return NULL;        /* can't allocate */
  23.     node->next = *s;
  24.     node->val = v;
  25.     if (*s == NULL) node->size = 1;
  26.     else node->size = (*s)->size + 1;
  27.     *s = node;
  28.     return *s;
  29. }
  30.  
  31. Re_node Pop(s)
  32. Stack *s;
  33. {
  34.     Re_node node;
  35.     Stack temp;
  36.  
  37.     if (s == NULL || *s == NULL) return NULL;
  38.     else {
  39.         temp = *s;
  40.         node = (*s)->val;
  41.         *s = (*s)->next;
  42.         free(temp);
  43.         return node;
  44.     }
  45. }
  46.  
  47. Re_node Top(s)
  48. Stack s;
  49. {
  50.     if (s == NULL) return NULL;
  51.     else return s->val;
  52. }
  53.  
  54. int Size(s)
  55. Stack s;
  56. {
  57.     if (s == NULL) return 0;
  58.     else return s->size;
  59. }
  60.  
  61. /************************************************************************/
  62. /*                                                                      */
  63. /*    the following routines manipulate sets of positions.        */
  64. /*                                                                      */
  65. /************************************************************************/
  66.  
  67. int occurs_in(n, p)
  68. int n;
  69. Pset p;
  70. {
  71.     while (p != NULL)
  72.         if (n == p->posnum) return 1;
  73.         else p = p->nextpos;
  74.     return 0;
  75. }
  76.  
  77. /* pset_union() takes two position-sets and returns their union.    */
  78.  
  79. Pset pset_union(s1, s2)
  80. Pset s1, s2;
  81. {
  82.     Pset hd, curr, new = NULL;
  83.  
  84.     hd = NULL; 
  85.     curr = NULL;
  86.     while (s1 != NULL) {
  87.         if (!occurs_in(s1->posnum, s2)) {
  88.             new_node(Pset, new, new);
  89.             if (new == NULL) return NULL;
  90.             new->posnum = s1->posnum;
  91.             if (hd == NULL) hd = new;
  92.             else curr->nextpos = new;
  93.         }
  94.         curr = new;
  95.         s1 = s1->nextpos;
  96.     }
  97.     if (hd == NULL) hd = s2;
  98.     else curr->nextpos = s2;
  99.     return hd;
  100. }
  101.  
  102. /* create_pos() creates a position node with the position value given,
  103.    then returns a pointer to this node.                    */
  104.  
  105. Pset create_pos(n)
  106. int n;
  107. {
  108.     Pset x;
  109.  
  110.     new_node(Pset, x, x);
  111.     if (x == NULL) return NULL;
  112.     x->posnum = n;
  113.     x->nextpos = NULL;
  114.     return x;
  115. }
  116.  
  117. /* eq_pset() takes two position sets and checks to see if they are
  118.    equal.  It returns 1 if the sets are equal, 0 if they are not.    */
  119. int
  120. subset_pset(s1, s2)
  121. Pset s1, s2;
  122. {
  123.     int subs = 1;
  124.  
  125.     while (s1 != NULL && subs != 0) {
  126.         subs = 0;
  127.         while (s2 != NULL && subs != 1)
  128.             if (s1->posnum == s2->posnum) subs = 1;
  129.             else s2 = s2->nextpos;
  130.         s1 = s1->nextpos;
  131.     }
  132.     return subs;
  133. }    
  134.  
  135. int eq_pset(s1, s2)
  136. Pset s1, s2;
  137. {
  138.     return subset_pset(s1, s2) && subset_pset(s2, s1);
  139. }
  140.  
  141. int
  142. word_exists(word, wordlen, line, linelen)
  143. unsigned char *word, *line;
  144. int wordlen, linelen;
  145. {
  146.     unsigned char oldchar, *lineend = line+linelen;
  147.     int i;
  148.  
  149.     i = 0;
  150.     while(line<lineend) {
  151.         if (!isalnum(line[i])) {
  152.             oldchar = line[i];
  153.             line[i] = '\0';
  154.             if (!strncmp(line, word, wordlen)) {
  155.                 line[i] = oldchar;
  156.                 return 1;
  157.             }
  158.             line[i] = oldchar;
  159.             line += i + 1;
  160.             i = 0;
  161.         } else i++;
  162.     }
  163.     return 0;
  164. }
  165.